<?php
/**
 * @title 173. 二叉搜索树迭代器 - 队列
 * @author start2004
 */

// ini_set("memory_limit", "128M");

class BSTIterator {
    /**
     * @param TreeNode $root
     */
    function __construct($root) {
        /**
         * @since 2020-08-17 队列, 降序
         */
        $this->list = self::find($root);
    }

    /**
     * @title tree转list
     * @author start2004
     * @since 2020-08-17 Created
     *
     * @param $root
     */
    public function find($root){
        /**
         * @since 2020-08-17 结果集
         */
        $result = [];

        /**
         * @since 2020-08-17 右子树
         */
        if($root->right !== null){
            $result = self::find($root->right);
        } else {}

        /**
         * @since 2020-08-17 root
         */
        $result[] = $root->val;

        /**
         * @since 2020-08-17 左子树
         */
        if($root->left !== null){
            $result = array_merge($result, self::find($root->left));
        } else {}

        /**
         * @return
         */
        return $result;
    }

    /**
     * @return the next smallest number
     * @return Integer
     */
    function next() {
        /**
         * @since 2020-08-17 出列
         */
        $val = array_pop($this->list);

        /**
         * @return
         */
        return $val;
    }

    /**
     * @return whether we have a next smallest number
     * @return Boolean
     */
    function hasNext() {
        /**
         * @since 2020-08-17 检查队列长度
         */
        if(count($this->list)>=1){
            return true;
        } else {
            return false;
        }
    }
}



/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.17_3.php
 */
$datas = [
    [
        ["BSTIterator","next","next","hasNext","next","hasNext","next","hasNext","next","hasNext"],
        [[[7,3,15,null,null,9,20]],[null],[null],[null],[null],[null],[null],[null],[null],[null]],
    ],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    $obj = new BSTIterator($xhprof->tree($data[1][0][0]));

    for ($i=1; $i<count($data[0]); $i++){
        $result = $obj->$data[0][$i]();
        if($result === true){
            echo "true";
        } elseif($result === false) {
            echo "false";
        } else {
            echo $result;
        }
        echo PHP_EOL;
    }
    echo str_repeat(PHP_EOL, 3);
}
$xhprof->end();
